#include <iostream>
using namespace std;

/// @brief 将以k为根的子树调整为大根堆
/// @param A
/// @param k
/// @param len
void HeadAdjust(int A[], int k, int len)
{
    A[0] = A[k]; // A[0]暂存子树的根节点
    for (int i = 2 * k; i <= len; i *= 2)
    { // 沿key较大的子节点想下筛选
        if (i < len && A[i] < A[i + 1])
        {
            i++; // 取key较大的子节点的下标(取左右子节点中更大的那个下标i)
        }
        if (A[0] >= A[i])
        {
            break; // 筛选结束
        }
        else
        {
            A[k] = i; // 将A[i]调整到双亲节点上
            k = i;    // 修改k值，以便继续向下筛选
        }
    }
    A[k] = A[0]; // 被筛选节点的值放入最终位置
}

/// @brief 建立大根堆
/// @param A
/// @param len
void BuildMaxHeap(int A[], int len)
{
    for (int i = len / 2; i > 0; i--) // 从后往前调整所有非终端节点
    {
        HeadAdjust(A, i, len);
    }
}

/// @brief 堆排序的完整逻辑
/// @param A
/// @param len
void HeadSort(int A[], int len)
{
    BuildMaxHeap(A, len); // 初始建堆
    for (int i = len; i > 1; i--)
    {                            // n-1趟的交换和建堆过程
        swap(A[i], A[1]);        // 堆顶元素和堆底元素交换
        HeadAdjust(A, 1, i - 1); // 把剩余的待排序元素整理成堆
    }
}
